//实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xⁿ ）。
//
//
//
// 示例 1：
//
//
//输入：x = 2.00000, n = 10
//输出：1024.00000
//
//
// 示例 2：
//
//
//输入：x = 2.10000, n = 3
//输出：9.26100
//
//
// 示例 3：
//
//
//输入：x = 2.00000, n = -2
//输出：0.25000
//解释：2-2 = 1/22 = 1/4 = 0.25
//
//
//
//
// 提示：
//
//
// -100.0 < x < 100.0
// -231 <= n <= 231-1
// n 是一个整数
// 要么 x 不为零，要么 n > 0 。
// -104 <= xⁿ <= 104
//
//
// Related Topics 递归 数学 👍 1181 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function myPow(x: number, n: number): number {

    if (n === 0 || x === 1) {
        return 1;
    }
    const isNegative = n < 0;
    n = Math.abs(n);
    let ans: number = x;
    let i = 1;//? 计数，乘了几个x了 while (i * 2 <= n)
    while (i * 2 <= n) {
        //? 如果还可以平方，就平方
        ans *= ans;
        i *= 2;
    }
    //? 剩下的不能平方的次数，再一个个的乘
    while (i < n) {
        ans *= x;
        i++;
    }
    return isNegative ? 1 / ans : ans;
};
//leetcode submit region end(Prohibit modification and deletion)
//? 快速幂算法
var myPow2 = function(x, n) {
    if(n == 0) return 1;
    if(n < 0) return 1 / myPow2(x, -n);
    if(n % 2) return x * myPow2(x, n - 1);
    return myPow2(x*x, n / 2);
};
